package exerise;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Created by jimmy on 2019/3/13.
 * 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符。
 * '*' 匹配零个或多个前面的元素。
 * 匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
 * <p>
 * 说明:
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 示例 1:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a*"
 * 输出: true
 * 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
 * 示例 3:
 * <p>
 * 输入:
 * s = "ab"
 * p = ".*"
 * 输出: true
 * 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
 * 示例 4:
 * <p>
 * 输入:
 * s = "aab"
 * p = "c*a*b"
 * 输出: true
 * 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
 * 示例 5:
 * <p>
 * 输入:
 * s = "mississippi"
 * p = "mis*is*p*."
 * 输出: false
 */
public class Ex10 {

    public static void main(String[] args) {
        String s = "abcd";
        String p = "a*b*";
        Pattern pattern = Pattern.compile(p);
        Matcher matcher = pattern.matcher(s);
        System.out.println("matcher == " + matcher.matches());

        Ex10 ex10 = new Ex10();
        boolean result = ex10.isMatch(s, p);
        System.out.println("result == " + result);
        boolean result2 = ex10.isMatch2(s, p);
        System.out.println("result2 == " + result2);
    }

    public boolean isMatch(String s, String p) {
        int ns = s.length();
        int np = p.length();
        if (np == 0 && ns != 0) return false;
        if (ns == 0) {
            if (np == 0) return true;
            if (np % 2 == 1) return false;
            int i = 1;
            while (i < np && p.charAt(i) == '*' && p.charAt(i - 1) != '*') {
                i += 2;
            }
            return i == np + 1;
        }
        if (p.charAt(np - 1) == s.charAt(ns - 1) || p.charAt(np - 1) == '.') {
            return isMatch(s.substring(0, ns - 1), p.substring(0, np - 1));
        }
        if (np > 1 && p.charAt(np - 1) == '*') {
            if (p.charAt(np - 2) != s.charAt(ns - 1) && p.charAt(np - 2) != '.') {
                return isMatch(s, p.substring(0, np - 2));
            } else {
                return isMatch(s.substring(0, ns - 1), p) ||
                        isMatch(s, p.substring(0, np - 1)) ||
                        isMatch(s, p.substring(0, np - 2));
            }
        }
        return false;
    }

    public boolean isMatch2(String s, String p) {
        int ns = s.length() + 1;
        int np = p.length() + 1;
        boolean[][] matched = new boolean[ns][np];
        //当s字符串为空的特殊处理

        //f(0, 0)表示s字符串为空，p字符串为空的情形
        matched[0][0] = true;
        //状态转移过程
        for (int i = 0; i < ns; i++) {
            for (int j = 1; j < np; j++) {
                if (i > 0 && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))) {
                    matched[i][j] = matched[i - 1][j - 1];
                }
                if (j > 1 && p.charAt(j - 1) == '*') {
                    if (i == 0 || (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.')) {
                        matched[i][j] = matched[i][j - 2];
                    } else {
                        matched[i][j] = matched[i - 1][j] || matched[i][j - 1] || matched[i][j - 2];
                    }
                }
            }
        }
        return matched[ns - 1][np - 1];
    }

}
